package com.hr.leetcode.栈与队列;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author 周恒哲
 * @date 2020/05/11
 * 总体思路：首先给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，把他们的右括号放入map中，通过键值去判断
 * 遍历String下标来获得每一个字母（charAt（）方法获得对应下标的字符），判断遍历出来的是否在map中，在的话就输出栈的top元素，然后通过键去获得map中的值来和top判断，不等返回false，等于重复上述
 **/
public class _20_有效的括号 {
    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)){
                //获取堆栈的顶部元素。如果堆栈为空，则将值设置为“#”
                char top=stack.empty()?'#':stack.pop();
                //如果此括号的映射与堆栈的顶部元素不匹配，则返回false。
                if (top!=map.get(c)){
                    return false;
                }
            }else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}
